The present invention relates to a method and apparatus for performing finite field and integer arithmetic.
Elliptic Curve(EC) cryptography over a finite field require arithmetic operations of addition, multiplication, squaring and inversion. Additionally, subtraction operations are also required if the field is not of characteristic two. Modular arithmetic operations are also required, for example in computing signatures, however these operations are required less frequently than the finite field operations. EC cryptography as an example, requires the full complement of modular and finite field operations, addition, subtraction, multiplication and inversion.
Field sizes for cryptography tend to be relatively large, requiring fast, dedicated processors to perform the arithmetic operations in an acceptable time. Thus there have been numerous implementations of either fast modular arithmetic processors or dedicated processors for performing arithmetic operations in F2n. The use of special purpose or dedicated processors is well known in the art. These processors are generally termed coprocessors and are normally utilized in a host computing system, whereby instructions and control is provided to the coprocessor from a main processor.
Traditionally RSA was the encryption system of choice, however with the advent of superior and more secure EC cryptography the need for processors that perform modular exponentiation exclusively is becoming less imperative. However, while users are in transition from RSA cryptography to EC cryptography there is a need for an arithmetic processor that supports both these operations, with little or no penalty in performance and cost.
It is an object of the invention to provide a processor that combines finite field arithmetic and integer arithmetic and for providing the operations required for EC cryptography, and modular exponentiation as required for example in RSA cryptography.
It is a further object of the invention to provide an arithmetic processor design that may be scaled to different field or register sizes.
A still further object of the invention is to provide an arithmetic processor that may be used with different field sizes.
A still further object of the invention is to provide an arithmetic processor that is capable of being scaled to provide an increase in speed when performing multi-sequence operations by simultaneously executing multiple steps in the sequence.
In accordance with this invention there is provided an arithmetic processor comprising:
(a) an arithmetic logic unit having a plurality of arithmetic circuits each for performing a group of associated arithmetic operations, the arithmetic logic unit having an operand input data bus for receiving operand data thereon and a result data output bus for returning the results of said arithmetic operations thereon;
(b) a register file coupled to said operand data bus and said result data bus; and
(c) a controller coupled to said ALU and said register file, said controller selecting one of said plurality of arithmetic circuits in response to a mode control signal requesting an arithmetic operation and for controlling data access between said register file and said ALU and whereby said register file is shared by said arithmetic circuits.
In accordance with a further embodiment of the invention, there is provided a processor that includes finite field circuitry and integer arithmetic circuitry and which includes general-purpose registers, and special-purpose registers.
In accordance with a further embodiment of the invention there is provided an arithmetic processor that performs both finite field arithmetic and integer arithmetic and in which both special purpose registers and general purpose registers, and arithmetic circuits, are shared. For this purpose, a polynomial basis for the finite field hardware will be assumed, since this basis is similar to the standard radix-power basis of the integers.